
/**
 * 0 onverkend, 1 muur, 2 geen muur
 */

package maze;

import java.util.ArrayList;
import java.util.List;
import java.util.Vector;

public class Maze {
	double SECTOR_WIDTH = 40.0;
	ArrayList<Barcode> barcodes;
	
	/**
	 * constructors
	 */
	public Maze(int size) {
		this.size = size;
		data = new char[size+1][size*2 +1];
		barcodes = new ArrayList<Barcode>();
	}
	
	public Maze(char[][] source) {
		this.size = ((source.length-1)>((source[0].length-1)/2))?(source.length-1):((source[0].length-1)/2);
		maxx = (source[0].length-1)/2-1;
		maxy = (source.length-1)-1;
		data = new char[this.size+1][this.size*2 +1];
		for(int i = 0; i<source.length; i++) {
			for(int j=0; j<source[0].length;j++) {
				data[size+1-source.length+i][j] = source[i][j];
			}
		}
		barcodes = new ArrayList<Barcode>();
	}
	
	public Maze(char[][] source, int minx, int maxx, int miny, int maxy) {
		this.size = ((source.length-1)>((source[0].length-1)/2))?(source.length-1):((source[0].length-1)/2);
		this.minx = minx;
		this.maxx = maxx;
		this.miny = miny;
		this.maxy = maxy;
		data = new char[this.size+1][this.size*2 +1];
		for(int i = 0; i<source.length; i++) {
			for(int j=0; j<source[0].length;j++) {
				data[size+1-source.length+i][j] = source[i][j];
			}
		}
		barcodes = new ArrayList<Barcode>();
	}
	
	public ArrayList<Barcode> getBarcodes(){
		return barcodes;
	}
	/**
	 * returns the barcode from the string if there is one
	 * @param barcode
	 * @return null if there is no barcode with that string
	 */
	public Barcode getBarcodeOnString(String barcode){
		for(int i=0; i<barcodes.size(); i++){
			Barcode barcodeTemp = barcodes.get(i);
			if(barcodeTemp.getCode().equals(barcode)){
				return barcodeTemp;
			}
		}
		return null;
	}
	public void addBarcode(int xPos, int yPos, String BC, int direction){
		barcodes.add(new Barcode(xPos,yPos,BC,direction));
	}
	
	static int xdelta(Direction dir) {
		switch(dir) {
		case EAST:
			return 1;
		case WEST:
			return -1;
		default:
			return 0;
		}
	}

	static int ydelta(Direction dir) {
		switch(dir) {
		case SOUTH:
			return -1;
		case NORTH:
			return 1;
		default:
			return 0;
		}
	}
		
	/**
	 * maze implementation
	 */
	//x+ is EAST
	//y+ is NORTH
	//used to bring other Mazes in the same coordinate system
	private Coordinate offset = new Coordinate(0,0);
	private int size = 32; //12.8 meter, so the capacity increase probably won't be used
	private char data[][] = new char[size+1][2*size+1];
	private int rot = 0; //how many 90 degree rotations (clockwise) compared to how the map started
	//keep track of max/min to avoid overflows
	private int minx = 0;
	private int miny = 0;
	private int maxx = 0;
	private int maxy = 0;
	
	private int positivemodulo(int val, int mod) {
		mod = Math.abs(mod); //no negative modulo allowed
		mod = (mod==0)?1:mod; //no zero modulo either
		while(val<0) val+= mod; //increase val until we're sure it's positive
		return val%mod;
	}
	
	//resizes the matrix if necessary
	private void updateBounds(Coordinate calculated) {
		int tminx = Math.min(minx, calculated.x);
		int tmaxx = Math.max(maxx, calculated.x);
		int tminy = Math.min(miny, calculated.y);
		int tmaxy = Math.max(maxy, calculated.y);
		while((tmaxx-tminx+1)>size || (tmaxy-tminy+1)>size) sizeUp();
		minx = tminx;
		maxx = tmaxx;
		miny = tminy;
		maxy = tmaxy;
	}
	
	//we need to go bigger!
	private void sizeUp() {
		System.out.println("size-up! from "+size+" to "+(2*size));
		char temp[][] = new char[2*size+1][4*size+1];
		//top left block
		for(int y = 0; y<-miny; y++) { //min* is 0 or less
			for(int x = 0; x<=((maxx+1)*2); x++) { //max* is 0 or more
				temp[y][x] = data[y][x];
			}
		}
		//bottom left block
		for(int y = size; y>=size-maxy-1; y--) {
			for(int x = 0; x<=((maxx+1)*2); x++) {
				temp[y+size][x] = data[y][x];
			}
		}
		//top right block
		for(int y = 0; y<-miny; y++) {
			for(int x = size*2; x>2*size+2*minx; x--) {
				temp[y][x+2*size] = data[y][x];
			}
		}
		//bottom right block
		for(int y = size; y>=size-maxy-1; y--) {
			for(int x = size*2; x>2*size+2*minx; x--) {
				temp[y+size][x+2*size] = data[y][x];
			}
		}
		
		size*=2;
		data = new char[size+1][2*size+1];
		for(int y = 0; y<size+1; y++) {
			for(int x = 0; x<2*size+1; x++) {
				data[y][x] = temp[y][x];
			}
		}
	}
	
	public Coordinate reverseTransform(Coordinate coord) {
		Coordinate newcoord = new Coordinate(0,0);
		newcoord.x = coord.x;
		newcoord.y = coord.y;
		//reverse offset
		newcoord.x = newcoord.x+offset.x;
		newcoord.y = newcoord.y+offset.y;
		//reverse rotation
		for(int i=0; i<rot; i++) {
			int temp = newcoord.y;
			newcoord.y = -newcoord.x;
			newcoord.x = temp;
		}
		return coord;
	}
	
	private Coordinate sectorToArray(Coordinate local, Direction wall, boolean ownCoordinates) {
		Coordinate matrix = local;
		if(!ownCoordinates) {
			//apply rotation
			for(int i=0; i<rot; i++) {
				int temp = matrix.x;
				matrix.x = -matrix.y;
				matrix.y = temp;
			}
			switch(rot) {
			case 1:
				wall = wall.left();
				break;
			case 2:
				wall = wall.opposite();
				break;
			case 3:
				wall = wall.right();
				break;
			}
			/*
			matrix.x = positivemodulo(matrix.x+offset.x,size); //apply offset and normalize
			matrix.y = positivemodulo(-matrix.y-1-offset.y,size); //apply offset and normalize while transforming to "y+ is SOUTH"
			*/
			matrix.x = matrix.x-offset.x;
			updateBounds(new Coordinate(matrix.x,matrix.y-offset.y));
			matrix.y = -matrix.y-2+offset.y;

		} else {
			/*
			matrix.x = positivemodulo(matrix.x,size); //normalize
			matrix.y = positivemodulo(-matrix.y-1,size); //normalize while transforming to "y+ is SOUTH"
			*/
			updateBounds(matrix);
			matrix.y = -matrix.y-2;
		}
		//calculate position in matrix
		switch(wall) {
		case NORTH:
			matrix.x = positivemodulo(matrix.x*2 + 1,size*2+1);
			matrix.y = positivemodulo(matrix.y,size+1);
			break;
		case SOUTH:
			matrix.x = positivemodulo(matrix.x*2 + 1,size*2+1);
			matrix.y = positivemodulo(matrix.y + 1,size+1);
			break;
		case WEST:
			matrix.x = positivemodulo(matrix.x*2,size*2+1);
			matrix.y = positivemodulo(matrix.y+1,size+1);
			break;
		case EAST:
			matrix.x = positivemodulo(matrix.x*2 + 2,size*2+1);
			matrix.y = positivemodulo(matrix.y+1,size+1);
			break;
		}
		return matrix;
	}
	
	/**
	 * Reads the specified wall from sector (x,y).
	 * ownCoordinates: if false, this function will use the coordinate system that was matched to another maze
	 * 				  otherwise, it will use its own local coordinates
	 */
	public char read(int x, int y, Direction wall, boolean ownCoordinates) {
		Coordinate temp = sectorToArray(new Coordinate(x,y),wall,ownCoordinates);
		return data[temp.y][temp.x];
	}

	
	public void write(int x, int y, Direction wall, char value, boolean ownCoordinates) {
		Coordinate temp = sectorToArray(new Coordinate(x,y),wall,ownCoordinates);
		data[temp.y][temp.x] = value;
	}

	/**
	 * matches the coordinate system to another maze where
	 * (localx,localy) on this maze corresponds to (targetx,targety) on the target maze
	 * returns false if the points can't be matched, true on success
	 */
	public boolean match(int localx1, int localy1, int targetx1, int targety1, int localx2, int localy2, int targetx2, int targety2) {
		//the given points are the same
		if((localx1-localx2)==0 && (localy1-localy2)==0) return false;
		//calculate differences
		int lxd = localx2 - localx1;
		int lyd = localy2 - localy1;
		int txd = targetx2 - targetx1;
		int tyd = targety2 - targety1;
		//no rotation change
		if(lxd==txd && lyd==tyd) rot = 0;
		//1 rotation
		else if(lxd==-tyd && lyd==txd) rot = 1;
		//2
		else if(lxd==-txd && lyd==-tyd) rot = 2;
		//3
		else if(lxd==tyd && lyd==-txd) rot = 3;
		//the points can't match
		else return false;
		//apply the rotation
		for(int i=0; i<rot; i++) {
			int temp = localx1;
			localx1 = -localy1;
			localy1 = temp;
		}
		//calculate the differences
		offset.x = localx1-targetx1;
		offset.y = localy1-targety1;
		return true;
	}
	
	/**
	 * matches the coordinate system to another maze where
	 * (localx,localy) on this maze corresponds to (targetx,targety) on the target maze
	 * and locald corresponds to targetd
	 * returns false if the points can't be matched, true on success
	 */
	public boolean match(int localx, int localy, int targetx, int targety, Direction locald, Direction targetd) {
		//no rotation change
		if(locald==targetd) rot = 0;
		//1 rotation
		else if(targetd==locald.right()) rot = 1;
		//2
		else if(targetd==locald.opposite()) rot = 2;
		//3
		else if(targetd==locald.left()) rot = 3;
		//the points directions
		else return false;
		//apply the rotation
		for(int i=0; i<rot; i++) {
			int temp = targetx;
			targetx = -targety;
			targety = temp;
		}
		//calculate the differences
		offset.x = localx-targetx;
		offset.y = localy-targety;
		return true;
	}
	
	public void draw(int posx, int posy) {
		String out = "";
		for(int y = 0; y<(size+1); y++) {
			for(int x = 0; x<(2*size+1); x++) {
				if((x==2*posx+1) && (y==size-posy+1)) {out+="*"; continue;}
				if(data[y][x]==1) {
					if(x%2!=0) out+= (((x-1)/2)<=maxx)?"_":"|";
					else out+=(((x-1)/2)<=maxx)?"|":"_";
				} else if(data[y][x]==0) out+="?";
				else out+=" ";
			}
			out+="\n";
		}
		out+="\n\n";
		System.out.println(out);
	}
	
	public void draw2(int minx, int maxx, int miny, int maxy, boolean ownCoordinates) {
		String out = "";
		for(int x = minx; x<=maxx; x++) {
			out +=" ";
			int val = read(x,maxy,Direction.NORTH,ownCoordinates);
			if(val==1) {
				out+="_";
			} else if(val==0) out+="?";
			else out+=" ";
		}
		out += "\n";
		for(int y = maxy; y>=miny; y--) {
			int val = read(minx,y,Direction.WEST,ownCoordinates);
			if(val==1) {
				out+="|";
			} else if(val==0) out+="?";
			else out+=" ";
			for(int x = minx; x<=maxx; x++) {
				val = read(x,y,Direction.SOUTH,ownCoordinates);
				if(val==1) {
					out+="_";
				} else if(val==0) out+="?";
				else out+=" ";
				val = read(x,y,Direction.EAST,ownCoordinates);
				if(val==1) {
					out+="|";
				} else if(val==0) out+="?";
				else out+=" ";
			}
			out+="\n";
		}
		out+="\ndone\n";
		System.out.println(out);
	}
	
	public int getMaxDistance(Location location, int rotation) {
		Location start = location;
		Coordinate startsector = new Coordinate((int)Math.floor(start.x/SECTOR_WIDTH),(int)Math.floor(start.y/SECTOR_WIDTH));
		if(startsector.x>maxx || startsector.y>maxy || startsector.x<minx || startsector.y<miny) return 0;//we're outside the maze (the fog of war is too thick to see anything)
		double rotRad = Math.toRadians(rotation);
		double rotCos = Math.cos(rotRad);
		if(((rotation+90)%360)==0) rotCos = 1.0/999999999999.9;
		double rotSin = Math.sin(rotRad);
		if((rotation%360)==0) rotSin = 1.0/999999999999.9;
		Location end = new Location(0,0); //let op: end.x en end.y horen niet bij elkaar
		Coordinate endsector = new Coordinate(0,0); // same here
		Direction wallx = Direction.EAST;
		Direction wally = Direction.NORTH;
		
		//shortest x
		endsector.x = startsector.x + ((rotCos<0.0)?0:1); //take the wall left or right depending on the angle
		if(rotCos<0.0) wallx = Direction.WEST;
		double diff = endsector.x*SECTOR_WIDTH - start.x;
		double distx = diff/rotCos; //de afstand die gereden moet worden om mogelijk een verticale muur te overschrijden
		end.y = start.y + distx*rotSin; //y-coordinaat van de intersectie met die verticale muur
		if(((rotation+90)%180)==0) distx = 99999999999999.9;

		//shortest y
		endsector.y = startsector.y + ((rotSin<0.0)?0:1); //take the wall up or down depending on the angle
		if(rotSin<0.0) wally = Direction.SOUTH;
		diff = endsector.y*SECTOR_WIDTH - start.y;
		double disty = diff/rotSin; //de afstand die gereden moet worden om mogelijk een horizontale muur te overschrijden
		end.x = start.x + disty*rotCos; //x-coordinaat van de intersectie met die horizontale muur
		if((rotation%180)==0) disty = 99999999999999.9;
		
		if(Math.abs(distx-disty)<0.001) {
			//randgeval waarbij de trace bijna exact door hoek gaat (valt normaal niet voor met echte data uit de simulator, maar never tempt the odds)
			if(distx<disty) {
				boolean wall = (read(startsector.x, startsector.y, wallx, true)!=1) && (read(startsector.x+xdelta(wallx), startsector.y+ydelta(wally), wally.opposite(), true)!=1);
				return (int)Math.round(distx + (wall?(double)(getMaxDistance(new Location(endsector.x*SECTOR_WIDTH+(0.001*rotCos),end.y+(0.001*rotSin)),rotation)+0.001):0.0));
			} else {
				boolean wall = (read(startsector.y, startsector.y, wally, true)!=1) && (read(startsector.x+xdelta(wallx), startsector.y+ydelta(wally), wallx.opposite(), true)!=1);
				return (int)Math.round(disty + (wall?(double)(getMaxDistance(new Location(end.x+(0.001*rotCos),endsector.y*SECTOR_WIDTH+(0.001*rotSin)),rotation)+0.001):0.0));
			}
		}
		if(distx<disty) { //we rijden over een verticale muur voor we over een horizontale rijden
			//geef de afstand tot de mogelijke muur en als er geen muur echt staat, de afstand van daar uit
			boolean wall = read(startsector.x, startsector.y, wallx, true)!=1;
			//ga 0.001cm verder (nodig om bij een negatieve richting in de juiste sector te starten)
			return (int)Math.floor(distx + (wall?(double)(getMaxDistance(new Location(endsector.x*SECTOR_WIDTH+(0.001*rotCos),end.y+(0.001*rotSin)),rotation)+0.001):0.0));
		} else {
			boolean wall = read(startsector.x, startsector.y, wally, true)!=1;
			return (int)Math.floor(disty + (wall?(double)(getMaxDistance(new Location(end.x+(0.001*rotCos),endsector.y*SECTOR_WIDTH+(0.001*rotSin)),rotation)+0.001):0.0));
		}
	}

	public int getConfirmedXsize() {
		return maxx-minx+1;
	}

	public int getConfirmedYsize() {
		return maxy-miny+1;
	}
	
	public int getMinX() {
		return minx;
	}
	
	public int getMinXWrap() {
		return positivemodulo(minx,size);
	}
	
	public int getMaxX() {
		return maxx;
	}
	
	public int getMinY() {
		return miny;
	}
	
	public int getMinYWrap() {
		return positivemodulo(miny,size);
	}
	
	public int getMaxY() {
		return maxy;
	}
	
	public int getSize() {
		return size;
	}
	
	public int getRotation() {
		return positivemodulo(rot*-90,360);
	}

	public List<Direction> getClearDirections(int x, int y, boolean ownCoordinates) {
		Coordinate temp = sectorToArray(new Coordinate(x,y),Direction.NORTH,ownCoordinates);
		boolean north = data[temp.y][temp.x] == 2;
		temp = sectorToArray(new Coordinate(x,y),Direction.EAST,ownCoordinates);
		boolean east = data[temp.y][temp.x] == 2;
		temp = sectorToArray(new Coordinate(x,y),Direction.SOUTH,ownCoordinates);
		boolean south = data[temp.y][temp.x] == 2;
		temp = sectorToArray(new Coordinate(x,y),Direction.WEST,ownCoordinates);
		boolean west = data[temp.y][temp.x] == 2;
		int amount = (north?1:0) + (east?1:0) + (south?1:0) + (west?1:0);
		List<Direction> possible=new ArrayList<Direction>();
//		Direction possible[] = new Direction[amount];
		int counter = 0;
		if(north) {possible.add(Direction.NORTH);}
		if(east) {possible.add(Direction.EAST);}
		if(south) {possible.add(Direction.SOUTH);}
		if(west) {possible.add(Direction.WEST);}
		return possible;
	}

	public char[][] getRawData() {
		return data.clone();
	}
	public Coordinate getCoordinateOfLocation(Location location){
		return new Coordinate((int) Math.floor((location.getX()/SECTOR_WIDTH)), (int) Math.floor((location.getY()/SECTOR_WIDTH)));
	}
	public Coordinate getCoordinateOfLocation(Location location, boolean ownCoordinates){
		if(ownCoordinates) return new Coordinate((int) Math.floor((location.getX()/SECTOR_WIDTH)), (int) Math.floor((location.getY()/SECTOR_WIDTH)));
		else {
			Coordinate retval = new Coordinate((int) Math.floor((location.getX()/SECTOR_WIDTH)), (int) Math.floor((location.getY()/SECTOR_WIDTH)));
			//apply rotation
			for(int i=0; i<rot; i++) {
				int temp = retval.x;
				retval.x = -retval.y;
				retval.y = temp;
			}
			retval.x = retval.x-offset.x;
			retval.y = retval.y-offset.y;
			return retval;
		}
	}
	public Location getLocationOfCoordinate(Coordinate coordinate){
		return new Location(coordinate.x*SECTOR_WIDTH+20,coordinate.y*SECTOR_WIDTH+20);
	}
	public List<Coordinate> getUnexploredCoordinates(){
		List<Coordinate> unexplored= new ArrayList<Coordinate>();
		for(int i = minx; i<=maxx; i++) {
			for(int j = miny; j<=maxy; j++) {
				if(read(i,j,Direction.EAST,true)==0) {
					if(!unexplored.contains(new Coordinate(i,j))) {
						unexplored.add(new Coordinate(i,j));
					}
					if(i+1<=maxx && !unexplored.contains(new Coordinate(i+1,j))) {
						unexplored.add(new Coordinate(i+1,j));
					}
				}
				if(read(i,j,Direction.NORTH,true)==0) {
					if(!unexplored.contains(new Coordinate(i,j))) {
						unexplored.add(new Coordinate(i,j));
					}
					if(j+1<=maxy && !unexplored.contains(new Coordinate(i,j+1))) {
						unexplored.add(new Coordinate(i,j+1));
					}
				}
			}
		}
		return unexplored;
	}
	public boolean hasThisSectorExplored(Coordinate coordinate){
		int x = coordinate.getX();
		int y = coordinate.getY();
		if(read(x,y,Direction.EAST,true)==0)
			return false;
		if(read(x,y,Direction.WEST,true)==0)
			return false;
		if(read(x,y,Direction.NORTH,true)==0)
			return false;
		if(read(x,y,Direction.SOUTH,true)==0)
			return false;
		return true;
	}
	
	//assumes the current sector is explored
	public Coordinate[] pathToClosestUnknown(int x, int y, boolean ownCoordinates) {
		class RecursiveCoordinate {
			Coordinate c;
			RecursiveCoordinate rc;
			RecursiveCoordinate(Coordinate c, RecursiveCoordinate rc) {
				this.c=c;
				this.rc=rc;
			}
			@Override
			public boolean equals(Object other) {
				try {
					return ((RecursiveCoordinate)other).c.equals(this.c);
				} catch(Exception e) {
					return false;
				}
			}
			@Override
			public int hashCode() {
				return this.c.hashCode();
			}
		}
		//actual method starts here
		if(!ownCoordinates) {
			//apply rotation
			for(int i=0; i<rot; i++) {
				int temp = x;
				x = -y;
				y = temp;
			}
			//apply offset
			x = x+offset.x;
			y = y+offset.y;
		}
		Vector<RecursiveCoordinate> passed = new Vector<RecursiveCoordinate>();
		Vector<RecursiveCoordinate> active = new Vector<RecursiveCoordinate>();
		active.add(new RecursiveCoordinate(new Coordinate(x,y),null)); //start from our current location
		RecursiveCoordinate target = null;

		while(active.size()>0) { //as long as there might be longer paths
			Vector<RecursiveCoordinate> temp = new Vector<RecursiveCoordinate>();
			for(RecursiveCoordinate rc : active) {
				passed.add(rc);
				//NORTH
				if(rc.c.y<=maxy) { //check whether we're not going out of bounds
					int val = read(rc.c.x,rc.c.y,Direction.NORTH,true); //get the wall we're looking at
					//create a new RecursiveCoordinate with the coordinate we're adding, referring to our current element of active
					RecursiveCoordinate t = new RecursiveCoordinate(new Coordinate(rc.c.x,rc.c.y+1), rc);
					if(val==2 && active.indexOf(t)==-1 && temp.indexOf(t)==-1 && passed.indexOf(t)==-1) { //if there's no wall, and the new coordinate hasn't been checked yet
						temp.add(t); //add it to the list of coordinates to use as active in the next iteration of the while-loop
					} else if(val==0) { //but if we have an unexplored wall
						target = rc; //then that's where we want to go
						temp.clear(); //and we don't want the while-loop to continue
						break; //neither do we want the for-loop to continue
					}
				}
				//EAST
				if(rc.c.x<=maxx) {
					int val = read(rc.c.x,rc.c.y,Direction.EAST,true);
					RecursiveCoordinate t = new RecursiveCoordinate(new Coordinate(rc.c.x+1,rc.c.y), rc);
					if(val==2 && active.indexOf(t)==-1 && temp.indexOf(t)==-1 && passed.indexOf(t)==-1) {
						temp.add(t);
					} else if(val==0) {
						target = rc;
						temp.clear();
						break;
					}
				}
				//SOUTH
				if(rc.c.y>=miny) {
					int val = read(rc.c.x,rc.c.y,Direction.SOUTH,true);
					RecursiveCoordinate t = new RecursiveCoordinate(new Coordinate(rc.c.x,rc.c.y-1), rc);
					if(val==2 && active.indexOf(t)==-1 && temp.indexOf(t)==-1 && passed.indexOf(t)==-1) {
						temp.add(t);
					} else if(val==0) {
						target = rc;
						temp.clear();
						break;
					}
				}
				//WEST
				if(rc.c.x>=minx) {
					int val = read(rc.c.x,rc.c.y,Direction.WEST,true);
					RecursiveCoordinate t = new RecursiveCoordinate(new Coordinate(rc.c.x-1,rc.c.y), rc);
					if(val==2 && active.indexOf(t)==-1 && temp.indexOf(t)==-1 && passed.indexOf(t)==-1) {
						temp.add(t);
					} else if(val==0) {
						target = rc;
						temp.clear();
						break;
					}
				}
				
			}
			active = temp; //prepare for the next iteration of the while loop
		}
		if(target==null || target.rc==null) return null;//the maze is explored || the current sector is not explored
		Vector<Coordinate> path = new Vector<Coordinate>();
		while(target.rc!=null) { //as long as we don't reach our starting point
			path.add(0,target.c); //prepend the coordinate from the target to the path
			target = target.rc; //go to the coordinate before it in the path
		}
		//path.removeElementAt(0); //we don't want the starting position included
		
		//change coordinate system
		if(!ownCoordinates) {
			for(Coordinate c : path) {
				//apply offset
				c.x = c.x-offset.x;
				c.y = c.y-offset.y;
				//apply rotation
				for(int it=0; it<rot; it++) {
					int temp = c.y;
					c.y = -c.x;
					c.x = temp;
				}
			}
		}
		return path.toArray(new Coordinate[1]);
	}
	
	//assumes the current sector is explored
	public Coordinate[] pathToClosestUnknown(int x, int y, Maze[] mazes) {
		if(mazes.length==0) return pathToClosestUnknown(x, y, true);
		class RecursiveCoordinate {
			Coordinate c;
			RecursiveCoordinate rc;
			RecursiveCoordinate(Coordinate c, RecursiveCoordinate rc) {
				this.c=c;
				this.rc=rc;
			}
			@Override
			public boolean equals(Object other) {
				try {
					return ((RecursiveCoordinate)other).c.equals(this.c);
				} catch(Exception e) {
					return false;
				}
			}
			@Override
			public int hashCode() {
				return this.c.hashCode();
			}
		}
		//actual method starts here
		Vector<RecursiveCoordinate> passed = new Vector<RecursiveCoordinate>();
		Vector<RecursiveCoordinate> active = new Vector<RecursiveCoordinate>();
		active.add(new RecursiveCoordinate(new Coordinate(x,y),null)); //start from our current location
		RecursiveCoordinate target = null;

		while(active.size()>0) { //as long as there might be longer paths
			Vector<RecursiveCoordinate> temp = new Vector<RecursiveCoordinate>();
			for(RecursiveCoordinate rc : active) {
				passed.add(rc);
				//NORTH
				if(rc.c.y<=maxy) { //check whether we're not going out of bounds
					int val = read(rc.c.x,rc.c.y,Direction.NORTH,true); //get the wall we're looking at
					boolean consensus = true;
					if(mazes[0] == null)
						System.out.println("mazes[0] is null");
					int otherValue = mazes[0].read(rc.c.x,rc.c.y,Direction.NORTH,false);
					//mazes[0].draw(x,y);
					for(Maze m : mazes) {
						int tempValue = m.read(rc.c.x,rc.c.y,Direction.NORTH,false); //get the opinion of the other mazes
						if(otherValue == 0 && tempValue != 0)
							otherValue = tempValue;
						else if(otherValue != 0 && tempValue == 0)
							tempValue = otherValue;
						consensus = consensus && tempValue==otherValue;
					}
					//create a new RecursiveCoordinate with the coordinate we're adding, referring to our current element of active
					RecursiveCoordinate t = new RecursiveCoordinate(new Coordinate(rc.c.x,rc.c.y+1), rc);
					boolean noWall = val==2 || (consensus && otherValue==2);
					boolean unexploredWall = val==0 && (otherValue==0 || (!consensus));
					if(noWall && active.indexOf(t)==-1 && temp.indexOf(t)==-1 && passed.indexOf(t)==-1) { //if there's no wall, and the new coordinate hasn't been checked yet
						temp.add(t); //add it to the list of coordinates to use as active in the next iteration of the while-loop
					} else if(unexploredWall) { //but if we have an unexplored wall
						target = rc; //then that's where we want to go
						temp.clear(); //and we don't want the while-loop to continue
						break; //neither do we want the for-loop to continue
					}
				}
				//EAST
				if(rc.c.x<=maxx) {
					int val = read(rc.c.x,rc.c.y,Direction.EAST,true);
					boolean consensus = true;
					int otherValue = mazes[0].read(rc.c.x,rc.c.y,Direction.EAST,false);
					for(Maze m : mazes) {
						int tempValue = m.read(rc.c.x,rc.c.y,Direction.EAST,false); //get the opinion of the other mazes
						if(otherValue == 0 && tempValue != 0)
							otherValue = tempValue;
						else if(otherValue != 0 && tempValue == 0)
							tempValue = otherValue;
						consensus = consensus && tempValue==otherValue;
					}
					RecursiveCoordinate t = new RecursiveCoordinate(new Coordinate(rc.c.x+1,rc.c.y), rc);
					boolean noWall = val==2 || (consensus && otherValue==2);
					boolean unexploredWall = val==0 && (otherValue==0 || (!consensus));
					if(noWall && active.indexOf(t)==-1 && temp.indexOf(t)==-1 && passed.indexOf(t)==-1) {
						temp.add(t);
					} else if(unexploredWall) {
						target = rc;
						temp.clear();
						break;
					}
				}
				//SOUTH
				if(rc.c.y>=miny) {
					int val = read(rc.c.x,rc.c.y,Direction.SOUTH,true);
					boolean consensus = true;
					int otherValue = mazes[0].read(rc.c.x,rc.c.y,Direction.SOUTH,false);
					for(Maze m : mazes) {
						int tempValue = m.read(rc.c.x,rc.c.y,Direction.SOUTH,false); //get the opinion of the other mazes
						if(otherValue == 0 && tempValue != 0)
							otherValue = tempValue;
						else if(otherValue != 0 && tempValue == 0)
							tempValue = otherValue;
						consensus = consensus && tempValue==otherValue;
					}
					RecursiveCoordinate t = new RecursiveCoordinate(new Coordinate(rc.c.x,rc.c.y-1), rc);
					boolean noWall = val==2 || (consensus && otherValue==2);
					boolean unexploredWall = val==0 && (otherValue==0 || (!consensus));
					if(noWall && active.indexOf(t)==-1 && temp.indexOf(t)==-1 && passed.indexOf(t)==-1) {
						temp.add(t);
					} else if(unexploredWall) {
						target = rc;
						temp.clear();
						break;
					}
				}
				//WEST
				if(rc.c.x>=minx) {
					int val = read(rc.c.x,rc.c.y,Direction.WEST,true);
					boolean consensus = true;
					int otherValue = mazes[0].read(rc.c.x,rc.c.y,Direction.WEST,false);
					for(Maze m : mazes) {
						int tempValue = m.read(rc.c.x,rc.c.y,Direction.WEST,false); //get the opinion of the other mazes
						if(otherValue == 0 && tempValue != 0)
							otherValue = tempValue;
						else if(otherValue != 0 && tempValue == 0)
							tempValue = otherValue;
						consensus = consensus && tempValue==otherValue;
					}
					RecursiveCoordinate t = new RecursiveCoordinate(new Coordinate(rc.c.x-1,rc.c.y), rc);
					boolean noWall = val==2 || (consensus && otherValue==2);
					boolean unexploredWall = val==0 && (otherValue==0 || (!consensus));
					if(noWall && active.indexOf(t)==-1 && temp.indexOf(t)==-1 && passed.indexOf(t)==-1) {
						temp.add(t);
					} else if(unexploredWall) {
						target = rc;
						temp.clear();
						break;
					}
				}
				
			}
			active = temp; //prepare for the next iteration of the while loop
		}
		if(target==null || target.rc==null) return null;//the maze is explored || the current sector is not explored
		Vector<Coordinate> path = new Vector<Coordinate>();
		while(target.rc!=null) { //as long as we don't reach our starting point
			path.add(0,target.c); //prepend the coordinate from the target to the path
			target = target.rc; //go to the coordinate before it in the path
		}
		//path.removeElementAt(0); //we don't want the starting position included
		
		return path.toArray(new Coordinate[1]);
	}

	
	public static void main(String[] args) {
		/*char mazedata[][] = {{2,1,2,1,2,1,2},{1,2,2,1,2,2,1},{1,2,1,1,1,2,1},{1,1,2,1,2,1,1}};
		Maze m = new Maze(mazedata);
		m.draw(-1,-1);
		System.out.println(((mazedata.length-1)>((mazedata[0].length-1)/2))?(mazedata.length-1):((mazedata[0].length-1)/2));
		m.write(-2,-2,Direction.NORTH,(char)1,true);
		m.write(-2,-2,Direction.EAST,(char)1,true);
		m.write(-2,-2,Direction.SOUTH,(char)1,true);
		m.write(-2,-2,Direction.WEST,(char)1,true);
		m.draw(-1,-1);
		m.write(-2, 1,Direction.NORTH,(char)1,true);
		m.write(-2, 1,Direction.EAST,(char)1,true);
		m.write(-2, 1,Direction.SOUTH,(char)1,true);
		m.write(-2, 1,Direction.WEST,(char)1,true);
		m.draw(-1,-1);
		m.write( 1,-2,Direction.NORTH,(char)1,true);
		m.write( 1,-2,Direction.EAST,(char)1,true);
		m.write( 1,-2,Direction.SOUTH,(char)1,true);
		m.write( 1,-2,Direction.WEST,(char)1,true);
		m.draw(-1,-1);
		m.write(-4,-4,Direction.NORTH,(char)1,true);
		m.write(-4,-4,Direction.EAST,(char)1,true);
		m.write(-4,-4,Direction.SOUTH,(char)1,true);
		m.write(-4,-4,Direction.WEST,(char)1,true);
		m.draw(-1,-1);
		System.out.println((int)m.read(0,0,Direction.NORTH,true));
		System.out.println((int)m.read(0,0,Direction.EAST,true));
		System.out.println((int)m.read(0,0,Direction.SOUTH,true));
		System.out.println((int)m.read(0,0,Direction.WEST,true));
		System.out.println((int)m.read(1,0,Direction.NORTH,true));
		System.out.println((int)m.read(1,0,Direction.EAST,true));
		System.out.println((int)m.read(1,0,Direction.SOUTH,true));
		System.out.println((int)m.read(1,0,Direction.WEST,true));		
		System.out.println((int)m.read(1,1,Direction.NORTH,true));
		System.out.println((int)m.read(1,1,Direction.EAST,true));
		System.out.println((int)m.read(1,1,Direction.SOUTH,true));
		System.out.println((int)m.read(1,1,Direction.WEST,true));		
		System.out.println(m.getMaxDistance(new Location(20.0,20.0),0));
		System.out.println(m.getMaxDistance(new Location(20.0,20.0),90));
		System.out.println(m.getMaxDistance(new Location(20.0,20.0),180));
		System.out.println(m.getMaxDistance(new Location(20.0,20.0),270));
		System.out.println(m.getMaxDistance(new Location(20.0,20.0),45));
		System.out.println(m.getMaxDistance(new Location(30.0,20.0),45));
		System.out.println(m.getMaxDistance(new Location(20.0,20.0),225));
		System.out.println(m.getMaxDistance(new Location(20.0,20.0),30));
		System.out.println(m.getMaxDistance(new Location(20.0,20.0),60));
		System.out.println(m.getMaxDistance(new Location(20.0,20.0),120));
		System.out.println(m.getMaxDistance(new Location(20.0,260.0),0));
		m.write(1,2,Direction.NORTH,(char)0,true);
		Coordinate[] path = m.pathToClosestUnknown(0,0,true);
		for(int i=0;i<path.length;i++) {
			System.out.print(path[i].x);
			System.out.print(",");
			System.out.println(path[i].y);
		}
		char mazedata0[][] = {{2,1,2,1,2,1,2},{1,2,2,1,2,2,1},{1,2,1,1,2,2,1},{1,1,2,1,2,1,1}};
		Maze m0 = new Maze(mazedata0);
		System.out.println("Maze 0");
		m0.draw2(0,2,0,2,true);
		char mazedata1[][] = {{1,2,1,1,2,2,1},{1,1,2,1,2,1,1},{2,1,2,1,2,1,2},{1,2,2,1,2,2,1}};
		Maze m1 = new Maze(mazedata1,0,2,-2,0);
		System.out.println("Maze 1 (own)");
		m1.draw2(0,2,-2,0,true);
		m1.match(0, -2, 0, 0, Direction.EAST, Direction.EAST);
		System.out.println("Maze 1 (matched)");
		m1.draw2(0, 2, 0, 2, false);
		char mazedata2[][] = {{1,1,2,2,1,1,2},{2,1,2,1,1,1,1},{2,1,2,1,2,2,1},{2,1,2,2,1,1,2}};
		Maze m2 = new Maze(mazedata2,-1,1,-2,0);
		System.out.println("Maze 2 (own)");
		m2.draw2(-1,1,-2,0,true);
		m2.match(-1, -2, 0, 0, Direction.EAST, Direction.EAST);
		System.out.println("Maze 2 (matched)");
		m2.draw2(0, 2, 0, 2, false);
		char mazedata3[][] = {{2,1,2,1,2,1,2},{1,2,2,2,2,2,1},{1,2,1,1,1,2,1},{1,1,2,1,2,1,1}};
		Maze m3 = new Maze(mazedata3);
		System.out.println("Maze 3 (own)");
		m3.draw2(0,2,0,2,true);
		m3.match(1, 1, 1, 1, Direction.NORTH, Direction.EAST);
		System.out.println("Maze 3 (matched)");
		m3.draw2(0,2,0,2, false);
		m3.match(2, 0, 0, 0, Direction.NORTH, Direction.EAST);
		System.out.println("Maze 3 (matched again)");
		m3.draw2(0,2,0,2, false);*/
		char mazedata[][] = {{2,1,2,1,2,1,2},{1,2,2,1,2,2,1},{1,2,1,1,1,2,1},{1,1,2,1,2,1,1}};
		Maze m = new Maze(mazedata);
		m.sizeUp();
		m.sizeUp();
		m.match(5, 3, 8, 2, Direction.EAST, Direction.EAST);
		m.draw2(-4, 2, 0, 5, false);
	}
}

/*

4x6

?_?_?_?_?
????| | |
?_?_|   |
|  _ _| |
|    _| |
| | |????
|_ _|????

{{0,1,0,1,0,1,0,1,0},
{0,0,0,0,1,2,1,2,1},
{0,1,0,1,1,2,2,2,1},
{1,2,2,1,2,1,1,2,1},
{1,2,2,2,2,1,1,2,1},
{1,2,1,2,1,0,0,0,0},
{1,1,2,1,1,0,0,0,0}}



4x4
?_?_?_?_?
|  _ _  |
|_|_ _  |
|  _ _  |
|_ _ _|_|

{{0,1,0,1,0,1,0,1,0},
{1,2,2,1,2,1,2,2,1},
{1,1,1,1,2,1,2,2,1},
{1,2,2,1,2,1,2,2,1},
{1,1,2,1,2,1,1,1,1}}

*/